;   This program is free software: you can redistribute it and/or modify
;   it under the terms of the GNU General Public License as published by
;   the Free Software Foundation, either version 3 of the License, or
;   (at your option) any later version.
;
;   This program is distributed in the hope that it will be useful,
;   but WITHOUT ANY WARRANTY; without even the implied warranty of
;   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;   GNU General Public License for more details.
;
;   You should have received a copy of the GNU General Public License
;   along with this program.  If not, see <http://www.gnu.org/licenses/>.
;
;程序名称:mazeX.asm
;功能:迷宫生成器及AStar寻径法范例
;环境:Windows视窗
;语言:X86 32汇编
;编译器:MASM32 
;编译环境:须安装MASM32, 请到http://www.masm32.com/下载 
;返回值:单一执行档,没有返回值
;破坏寄存器:不适用
;程序档数目:1 , 只须mazeX.asm即可编译(即以下全部代码),没有额外的inc,ico..
;
;编译方法:
;1.
;将(程式开始)到(程式结束)的代码覆制到一个文件,存成纯文字档(ascii),档名mazeX.asm
;执行
;\MASM32\BIN\Ml.exe /c /coff  mazeX.asm
;\MASM32\BIN\Link.exe /SUBSYSTEM:WINDOWS mazeX.obj
;若成功,即生成mazex.exe
;2.
;将(程式开始)到(程式结束)的代码覆制到MASM32 Editor上(masm32的编辑器)
;选project -> Assemble & Link
;若成功,即生成mazex.exe
;
;
;这个汇编小程式是最基本的迷宫生成和迷宫寻找最短路径代码
;以深度优先作算法的迷宫生成子程序:invoke RandomMaze,参数列..........
;以ASTAR 寻径算法的子桯序: invoke AStarFindPathproc,参数列..........
;主程序给出适当的参数便可以简单调用
;此外,范例有几个功能
;1.>Path<按键,预设由左上角至右下角的路径,再按一下清除
;2.滑鼠右键,清除路径
;3.滑鼠左键在地图上任意点击起点,再点击终点,路径即时生效


; -- 程式开始 ----
MazeSize equ 21  ;初始迷宫大小
wMaxMap equ 57  ;最大迷宫大小
hMaxMap equ 57  
wMinMap equ 3 ;最小迷宫大小
hMinMap equ 3
xStart equ 10
yStart equ 10
xMyMaze equ 100
yMyMaze equ 5
xBoardLine equ MazeSize  
yBoardLine equ MazeSize  ;same or diff
bwNewX equ 760
bwNewY equ 30
CellSize equ 21
boardW equ 850
boardH equ 720
Direction1GValue equ 10
IDM_NEW_BT equ 1000   ;按键定义
IDM_INC_BT equ 1001
IDM_DEC_BT equ 1002
IDM_APATH_BT equ 1003
;以下包含档,须安装masm32,并确定路径正确(路径可改)
include \masm32\include\masm32rt.inc
INCLUDE \MASM32\INCLUDE\advapi32.inc
INCLUDE \MASM32\INCLUDE\winmm.inc
INCLUDELIB \MASM32\LIB\advapi32.LIB
INCLUDELIB \MASM32\LIB\winmm.LIB
INCLUDE \MASM32\INCLUDE\msimg32.inc
INCLUDELIB \MASM32\LIB\msimg32.lib

WinMain proto :DWORD,:DWORD,:DWORD,:DWORD 
RandomMaze proto :DWORD,:DWORD,:DWORD,:DWORD,:DWORD
AStar_FindPath_proc proto :DWORD,:DWORD,:DWORD,:DWORD,:DWORD,:DWORD,:DWORD

.686
.DATA
ApathSetCount dd 0
;seed dd 0FFAABB11h      ;乱数种子
dwAsCnt dd 1
CellDirect dd 1,0,0,1,-1,0,0,-1
CellAddValue dd 1,MazeSize,-1,-MazeSize
DisplayApathflag dd 	0
xUserSource dd 0
yUserSource dd 0 
xUserTarget dd xBoardLine
yUserTarget dd yBoardLine
EdgeOffset label dword
 dd CellSize+6,0,3,CellSize+9
 dd 0,CellSize+6,CellSize+6,3
 dd 0,0,3,CellSize+9
 dd 0,0,CellSize+6,3
 wUserMap dd xBoardLine
 hUserMap dd  yBoardLine
 UserCellSize dd CellSize
NewMapFlag dd 0
QuitNow db "QUIT ?",0
UserInput db  20h,20h,20h,20h,20h,20h,20h,20h
UserInput_L equ $ - offset UserInput
ClassName db "SimpleWinClass",0 
AppName  db "Maze",0 
;MouseClick db 0
MenuName db "FIRSTMENU",0       ; The name of our menu in the resource file. 
statClass db "STATIC",0
szButton		db	'button',0
szButtonText	db	'New Map',0
szButtonText2	db	' + ',0
szButtonText3	db	' - ',0
szButtonText4	db	'> Path <',0
CreateStr db 'Create:'
CreateVal db 20h,20h,20h,20h,20h,20h,20h,20h
CreateStr_L equ $ - offset CreateStr
CreateTime dd 0,0
SolveStr db 'Solve:'
SolveVal db 20h,20h,20h,20h,20h,20h,20h,20h
SolveStr_L equ $ - offset SolveStr
db 20h,20h,20h,20h
SolveTime dd 0,0
CheckBlockWall label byte
db 00000001b
db 00000010b
db 00000100b
db 00001000b

.data? 
align 4
hInstance HINSTANCE ? 
CommandLine LPSTR ? 
hitpoint POINT <> 
hCur0 dd ?
G_hwnd dd ?
qwRnd64 dq ?
SourceTargetTempPosition dd ?,?,?,?
column_row_table dd wMaxMap*2 dup (?)
MazeBoard label byte 
db wMaxMap*hMaxMap dup  (?) 	;00001111b 跟MazeBoard的偏移代表xy, 0fh表示四墙
;若x=0或x= MazeW - 1表不左边界及右边界
;若y=0或x= MazeH - 1表不上边界及下边界
;起点可以由map中任一点定义

.code 
align 4
start: 
    invoke GetModuleHandle, NULL 
    mov    hInstance,eax 
    invoke GetCommandLine
    mov CommandLine,eax 
    invoke WinMain, hInstance,NULL,CommandLine, SW_SHOWDEFAULT 
    invoke ExitProcess,eax 

WinMain proc hInst:HINSTANCE,hPrevInst:HINSTANCE,CmdLine:LPSTR,CmdShow:DWORD 
    LOCAL wc:WNDCLASSEX 
    LOCAL msg:MSG 
    LOCAL hwnd:HWND 
    ;mov   wc.cbSize,SIZEOF WNDCLASSEX 
    mov   wc.cbSize,30h 
    mov   wc.style, CS_HREDRAW or CS_VREDRAW 
    mov   wc.lpfnWndProc, OFFSET WndProc 
    mov   wc.cbClsExtra,NULL 
    mov   wc.cbWndExtra,NULL 
    push  hInst 
    pop   wc.hInstance 
    ;mov   wc.hbrBackground,COLOR_WINDOW +1
    mov   wc.hbrBackground,COLOR_BTNFACE+1 
	
    ;mov   wc.hbrBackground,2  ;green
    mov   wc.lpszMenuName,OFFSET MenuName        ; Put our menu name here 
    mov   wc.lpszClassName,OFFSET ClassName 
     invoke LoadIcon,hInst,500
     mov   wc.hIcon,eax 
     mov wc.hIconSm,0
    invoke LoadCursor,NULL,IDC_ARROW 
    mov   wc.hCursor,eax 
    mov hCur0,eax
    invoke RegisterClassEx, addr wc 
	invoke CreateWindowEx,NULL,ADDR ClassName,ADDR AppName,\ 
	WS_OVERLAPPEDWINDOW,xMyMaze,\ 
	yMyMaze,boardW,boardH,NULL,NULL,\ 
	hInst,NULL 
	mov   hwnd,eax 
	mov G_hwnd,eax
	invoke ShowWindow, hwnd,SW_SHOWNORMAL 
	invoke UpdateWindow, hwnd 
    .WHILE TRUE 
                invoke GetMessage, ADDR msg,NULL,0,0 
                .BREAK .IF (!eax) 
                invoke TranslateMessage, ADDR msg 
                invoke DispatchMessage, ADDR msg 
    .ENDW 
	mov     eax,msg.wParam 
	ret 
WinMain endp 

WndProc proc hWnd:HWND, uMsg:UINT, wParam:WPARAM, lParam:LPARAM 
    LOCAL ps:PAINTSTRUCT 
    LOCAL rect:RECT 
    LOCAL Rct    :RECT
    LOCAL hDC    :DWORD
    LOCAL hPen      :DWORD
    LOCAL hPenOld   :DWORD
    LOCAL hBrush    :DWORD
    LOCAL hBrushOld :DWORD
    LOCAL OldCurType :DWORD
    LOCAL lb        :LOGBRUSH
    LOCAL xPosition	:DWORD	;pixel position X
    LOCAL yPosition	:DWORD	;pixel position Y
    LOCAL wCell	:DWORD
    LOCAL hCell	:DWORD
    LOCAL wwCell	:DWORD
    LOCAL hhCell	:DWORD
    LOCAL CellRangeCount:DWORD
    LOCAL NoShowPathFlag:DWORD
    LOCAL NoShowBigPathFlag:DWORD
    LOCAL WhichDirection	:DWORD
    LOCAL buffer1[128]:BYTE  ; these are two spare buffers
    LOCAL buffer2[128]:BYTE  ; for text manipulation etc..
   .If uMsg == WM_CREATE
		;以下建立按键
		invoke	CreateWindowEx,NULL,\
			offset szButton,offset szButtonText,\
			WS_CHILD or WS_VISIBLE,\
			bwNewX,bwNewY,65,22,\
			hWnd,IDM_NEW_BT,hInstance,NULL

		invoke	CreateWindowEx,NULL,\
			offset szButton,offset szButtonText2,\
			WS_CHILD or WS_VISIBLE,\
			bwNewX,bwNewY+30,30,22,\
			hWnd,IDM_INC_BT,hInstance,NULL

		invoke	CreateWindowEx,NULL,\
			offset szButton,offset szButtonText3,\
			WS_CHILD or WS_VISIBLE,\
			bwNewX+30,bwNewY+30,30,22,\
			hWnd,IDM_DEC_BT,hInstance,NULL

		invoke	CreateWindowEx,NULL,\
			offset szButton,offset szButtonText4,\
			WS_CHILD or WS_VISIBLE,\
			bwNewX,bwNewY+60,65,22,\
			hWnd,IDM_APATH_BT,hInstance,NULL
		
		rdtsc	 ; 开始计时

		mov CreateTime,eax
		mov CreateTime+4,edx
		invoke RandomMaze,wUserMap,hUserMap,xStart,yStart,ADDR MazeBoard  ;随机产生迷宫子程序

		rdtsc	;终止计时

		sub eax,CreateTime
		sbb edx,CreateTime +4
		mov ebx,200000
		div ebx
		mov CreateTime,eax
		mov ebx,20202020h
		mov edi,offset CreateVal
		mov [edi],ebx
		call print_AX
		mov dword ptr  [edi],'  sm'
		invoke InvalidateRect,G_hwnd,NULL,TRUE                ;redraw

      .elseif uMsg == WM_CLOSE
		invoke EndDialog, hWnd, NULL
		invoke DestroyWindow,hWnd 
		xor eax,eax
		ret

    .ELSEIF uMsg==WM_DESTROY 
		invoke PostQuitMessage,NULL 

;-------------------------------------------------------------------
      .elseif uMsg == WM_MOUSEMOVE
		;not yet

      .elseif uMsg == WM_RBUTTONDOWN 
		test dword ptr DisplayApathflag,1
		jz @f
		call ClearPath 
		mov ApathSetCount,0
		mov dword ptr DisplayApathflag,0
		invoke InvalidateRect,G_hwnd,NULL,TRUE                ;redraw
		@@:	
;-----------------------------------------------------------------------
     .ELSEIF uMsg==WM_LBUTTONDOWN 
	;侦测到滑鼠左键,比较是否2次有效按键,若是,则开始寻径
	cmp ApathSetCount,2
	jae LBUTTONx			;已清除,可定义
	
	mov ecx,ApathSetCount
	shl ecx,3			;x4
	mov eax,lParam 
	and eax,0FFFFh 
	mov hitpoint.x,eax 
	mov edx,lParam 		
	shr edx,16 
	mov hitpoint.y,edx 	
	
	mov SourceTargetTempPosition[ecx],0
	mov esi,offset column_row_table

@@:	mov eax,hitpoint.x
	cmp eax,[esi]
	jb LBUTTONx		;不在x坐标
	cmp eax,[esi+4]
	jb LBUTTON10
	inc SourceTargetTempPosition[ecx]
	add esi,8
	mov eax,SourceTargetTempPosition[ecx]
	cmp eax,wUserMap
	jb @b
	jmp LBUTTONx		;不在x坐标,走

LBUTTON10:			;在x坐标

	mov SourceTargetTempPosition[ecx+4],0
	mov esi,offset column_row_table

@@:	mov eax,hitpoint.y
	cmp eax,[esi]
	jb LBUTTONx		;不在x坐标
	cmp eax,[esi+4]
	jb LBUTTON20
	inc SourceTargetTempPosition[ecx+4]
	add esi,8
	mov eax,SourceTargetTempPosition[ecx+4]
	cmp eax,hUserMap
	jb @b
	jmp LBUTTONx		;不在y坐标,走

LBUTTON20:
	;得到 x,y tempPosition

	cmp ApathSetCount,1
	jnz CheckN30

	;第2mouse click

	call CheckNeighbour
	cmp eax,-1	
	jz LBUTTONx

CheckN30:
	mov eax,wUserMap
	mul SourceTargetTempPosition[ecx+4]
	add eax,SourceTargetTempPosition[ecx]
	add eax,offset MazeBoard
	or byte ptr [eax], 10000000b	;path flag
	or byte ptr [eax], 01000000b	;big dog flag
	mov dword ptr DisplayApathflag,1
	invoke InvalidateRect,G_hwnd,NULL,FALSE                ;redraw
	;
	inc ApathSetCount
	cmp ApathSetCount,2
	jnz LBUTTONx
@@:
	mov ecx,0
	push SourceTargetTempPosition[ecx]
	pop xUserSource
	push SourceTargetTempPosition[ecx+4]
	pop yUserSource
	push SourceTargetTempPosition[ecx+8]
	pop xUserTarget
	push SourceTargetTempPosition[ecx+12]
	pop yUserTarget
	mov dword ptr DisplayApathflag,1
	;------------------------------
	rdtsc	;开始计时
	mov SolveTime,eax
	mov SolveTime+4,edx
	;A Astar 寻径子程序
	invoke AStar_FindPath_proc,xUserSource,yUserSource,xUserTarget,yUserTarget,wUserMap,hUserMap,ADDR MazeBoard	;A*寻径子程序
	rdtsc	;终止计时
	sub eax,SolveTime
	sbb edx,SolveTime +4
	mov ebx,200000		;1 ns to  ?ms
	div ebx
	mov SolveTime,eax
	mov ebx,20202020h
	mov edi,offset SolveVal
	mov [edi],ebx
	call print_AX
	mov dword ptr  [edi],'  sm'
	invoke InvalidateRect,G_hwnd,NULL,TRUE                ;redraw
	;寻径结束
LBUTTONx:
;---------------------------------------------
     .elseif uMsg == WM_SIZE
	;no size action

    .ELSEIF uMsg==WM_PAINT 
	;重刷画面
	invoke BeginPaint,hWnd,ADDR ps
	mov hDC,eax
	
	;  ----------- draw CELL start ----------------

	invoke CreatePen,0,3,0h  ; black
	mov hPen, eax
	mov lb.lbStyle, BS_SOLID
	mov lb.lbColor, 0h       ; black

	mov lb.lbHatch, NULL
	invoke CreateBrushIndirect,ADDR lb
	mov hBrush, eax
	invoke SelectObject,hDC,hPen
	mov hPenOld, eax
	invoke SelectObject,hDC,hBrush
	mov hBrushOld, eax

	mov eax,UserCellSize
	add eax,6
	mov wCell,eax		;21 + 6  ,2条边
	mov hCell,eax		;21 + 6
	mov wwCell,eax
	mov hhCell,eax

	mov CellRangeCount,0
	mov edi,offset column_row_table
	mov ecx,wMaxMap*2 
	mov eax,-1
	rep stosd			;init

	mov esi,offset MazeBoard
	mov eax,hUserMap
	mul wUserMap
	mov ecx,eax
Draw10:
	push ecx
	push esi
	mov eax,esi
	sub eax,offset offset MazeBoard 

@@:	mov ebx,wUserMap			;37
	xor edx,edx
	div ebx	
	push edx			;columns
	; eax = rows , edx = columns
	mul wCell			; x 21+6
	mov yPosition,eax
	pop eax			;get columns
	mul hCell			; x 21 + 6
	mov xPosition,eax	
Draw15:
	mov ecx,0
	lodsb			;1???  1111  ;bit 7 mean step bit 0-3 mean wall
	mov bl,al
	mov NoShowPathFlag,0
	mov NoShowBigPathFlag,0
	test al,10000000b	
				;jz Draw20
	jz @f
	mov NoShowPathFlag,1
@@:
	test al,01000000b	
	jz @f
	mov NoShowBigPathFlag,1
@@:
	;------------
	pushad
	mov eax,UserCellSize
	shr eax,1			;/2
	mov ebx,eax
	add eax,xPosition
	mov ecx,eax
	add  eax,3			;;;;;;;;;;;
	add ecx,6
	add ebx,yPosition
	mov edx,ebx
	add ebx,3
	add edx,6

	push eax
	push ecx
	push esi
	sub esi,offset offset MazeBoard 		;0- ??
	dec esi				;因已lodsb
	cmp esi,wUserMap
	jae @f
	shl esi,3				;x8
	add esi,offset column_row_table
	sub eax,5		;4
	add ecx,5		;4
	mov [esi],eax
	mov [esi+4],ecx	
@@:	pop esi
	pop ecx
	pop eax
 	cmp NoShowPathFlag,0
	jz @f
	cmp NoShowBigPathFlag,0	;起点和终点画大圆
	jz Draw16
	; big path flag
	sub eax,2
	sub ebx,2
	add ecx,2
	add edx,2	
Draw16:
	invoke Ellipse,hDC, eax,ebx,ecx,edx 	;LeftRect,TopRect,RightRect,BottomRect

@@:	popad

Draw20:	push ecx
	rcr bl,1
	jnc Draw30
	;print edge,ecx 决定印上下左右
	mov edx,ecx
	shl edx,4		;x16
	mov eax,EdgeOffset[edx]
	add eax,xPosition
	mov ecx,EdgeOffset[edx+4]
	add ecx,yPosition
	invoke PatBlt,hDC,eax,ecx,EdgeOffset[edx+8],EdgeOffset[edx+12],BLACKNESS

Draw30:	pop ecx
	inc ecx	
	cmp ecx,4
	jb Draw20
	pop esi
	pop ecx
	inc CellRangeCount
	inc esi
	dec ecx
	jnz Draw10
	;以下输出文字及数值
	mov edi,offset UserInput
	mov eax,20202020h
	mov [edi],eax
	mov eax,wUserMap
	call print_AX
	mov edi,offset UserInput
	mov eax,[edi]
	mov [edi+4],eax
	mov byte ptr [edi+3],'x'
	;mov edi,offset UserInput
	invoke TextOut,hDC,bwNewX,bwNewY+90,ADDR UserInput ,UserInput_L - 1

	;------- print time text start --------------
	
	invoke TextOut,hDC,bwNewX,bwNewY+120,ADDR CreateStr ,CreateStr_L
	invoke TextOut,hDC,bwNewX,bwNewY+150,ADDR SolveStr ,SolveStr_L

	;------- print time text end --------------

	invoke SelectObject,hDC,hBrushOld
	invoke DeleteObject,hBrush
	invoke SelectObject,hDC,hPenOld
	invoke DeleteObject,hPen
	
	;  ----------- draw CELL end ----------------

	invoke ReleaseDC,hWnd,hDC	;以下移除暂时句柄
	invoke EndPaint,hWnd, ADDR ps 

;---------------------------------------------------------------
    .ELSEIF uMsg==WM_COMMAND 
	;以下侦测滑鼠是否按到指定区
	mov eax,wParam 
	.IF ax==IDM_NEW_BT 

		mov ApathSetCount,0
		mov dword ptr DisplayApathflag,0
		invoke RandomMaze,wUserMap,hUserMap,xStart,yStart,ADDR MazeBoard
		invoke InvalidateRect,G_hwnd,NULL,TRUE                ;redraw

	.ELSEIF ax==IDM_APATH_BT 

		xor dword ptr DisplayApathflag,1
		test dword ptr DisplayApathflag,1
		jnz APATH_BT10
		call ClearPath 
		mov ApathSetCount,0
		jmp APATH_BT20		

APATH_BT10:
		;xUserTarget dd xBoardLine
		
		cmp xUserTarget,xBoardLine
		jz @f
		mov eax,xUserTarget
		mov ebx,yUserTarget
		jmp APATH_BT15
		
@@:		mov eax,wUserMap
		dec eax
		mov ebx,hUserMap
		dec ebx
APATH_BT15:
		push eax
		call CheckNeighbour
		cmp eax,-1	
		pop eax
		jz APATH_BT30

		mov esi,wUserMap
		mov edi,hUserMap
		cmp xUserSource,esi
		ja APATH_BT30
		cmp eax,esi
		ja APATH_BT30
		cmp yUserSource,edi
		ja  APATH_BT30
		cmp ebx,edi
		ja  APATH_BT30	

		push eax
		rdtsc
		mov SolveTime,eax
		mov SolveTime+4,edx
		pop eax
		;开始寻径
		invoke AStar_FindPath_proc,xUserSource,yUserSource,eax,ebx,wUserMap,hUserMap,ADDR MazeBoard
		rdtsc
		sub eax,SolveTime
		sbb edx,SolveTime +4
		mov ebx,200000
		div ebx
		mov SolveTime,eax
		mov ebx,20202020h
		mov edi,offset SolveVal
		mov [edi],ebx
		;mov [edi+4],ebx
		;mov word ptr  [edi+4],'sm'
		call print_AX
		mov dword ptr  [edi],'  sm'
		mov ApathSetCount,2
APATH_BT20:
		invoke InvalidateRect,G_hwnd,NULL,TRUE                ;redraw

APATH_BT30:

	.ELSEIF ax==IDM_INC_BT 
	
	;make table tempCellAddValue dd 1,MazeSize,-1,-MazeSize

		cmp  wUserMap,wMaxMap
		jae UserLeave
		add wUserMap,2
		add hUserMap,2	

    ajustUser:
		mov ApathSetCount,0
		mov dword ptr DisplayApathflag,0

		mov eax,21 * CellSize
		xor edx,edx
		mov ebx,wUserMap
		div ebx
		dec eax
@@:
		mov UserCellSize,eax
		add eax,6
		mov ecx,0
		mov EdgeOffset[ecx],eax
		mov EdgeOffset[ecx+20],eax
		mov EdgeOffset[ecx+24],eax
		mov EdgeOffset[ecx+56],eax
		add eax,3
		mov EdgeOffset[ecx+12],eax
		mov EdgeOffset[ecx+44],eax
		;随机产生迷宫
		invoke RandomMaze,wUserMap,hUserMap,xStart,yStart,ADDR MazeBoard
		invoke InvalidateRect,G_hwnd,NULL,TRUE                ;redraw
	UserLeave:	
		xor eax,eax
		ret

	.ELSEIF ax==IDM_DEC_BT 

		cmp  wUserMap,wMinMap
		jbe UserLeave
		sub wUserMap,2
		sub hUserMap,2	
		jmp ajustUser

	.ELSE 		 ;exit

		invoke MessageBox, hWnd, OFFSET QuitNow, OFFSET AppName, MB_ICONINFORMATION + MB_YESNO
		.IF eax == IDYES
			invoke EndDialog, hWnd, NULL
			invoke DestroyWindow,hWnd 
			xor eax,eax
			ret
		.ENDIF	
        .ENDIF 

    .ELSE 
		invoke DefWindowProc,hWnd,uMsg,wParam,lParam 
		ret 
    .ENDIF 
		xor    eax,eax 
		ret 
WndProc endp 
;----------------------------------------------------------------------------------------------
;随机产生迷宫子程序
RandomMaze proc  wTempMaze:DWORD,hTempMaze:DWORD,xStartMaze:DWORD,yStartMaze:DWORD,addrMaze:DWORD

	LOCAL xMaze		:DWORD		
	LOCAL yMaze		:DWORD		
	LOCAL StackCount		:DWORD		
	LOCAL CellCount		:DWORD		
	LOCAL AddDecValue	:DWORD		
	LOCAL SourceWall		:DWORD		
	LOCAL OppositeWall		:DWORD		
	LOCAL LastCellDirect[4]	:DWORD		
	LOCAL tempCellAddValue[4]	:DWORD		
	LOCAL tempCellDirect[8]	:DWORD		
	LOCAL hStackMemory	:DWORD		
	LOCAL pStackMemory	:DWORD		

	;-------以下检查输入数据 ---------------------

	mov eax,wTempMaze    
	dec eax
	cmp eax,xStartMaze  	;迷宫宽是否
	jae @f			;大于等于起点x
	mov xStartMaze,0	;修改起点x
@@: 
	mov eax,hTempMaze    
	dec eax
	cmp eax,yStartMaze  	;迷宫高是否
	jae @f			;大于等于起点y
	mov yStartMaze,0	;修改起点y
@@:
	cmp wTempMaze,2	;检查宽,高大于等于2
	jb RandomMXX
 	cmp hTempMaze,2
	jb RandomMXX

	;-----以下申请内存栈 -------------

	mov eax,wTempMaze
	mul hTempMaze
	push eax
	mov ecx,16
	xor edx,edx
	div ecx
	mul ecx		
	shl eax,2		;x4   for dword
	add eax,1024		;至少1k

	invoke GlobalAlloc, GMEM_FIXED or GMEM_ZEROINIT,eax
	mov  hStackMemory,eax 
	invoke GlobalLock,hStackMemory 
	mov  pStackMemory,eax 
	pop ecx

	;----------以下初始化----------

	;mov ecx,xBoardLine	*  yBoardLine * 2
	mov edi,addrMaze
	mov al,0fh		;00001111b
	rep stosb	
	mov edi,0	
	;make table tempCellDirect dd 1,0,0,1,-1,0,0,-1	
 	mov dword ptr tempCellDirect[edi],1
 	mov dword ptr tempCellDirect[edi+4],0
 	mov dword ptr tempCellDirect[edi+8],0
 	mov dword ptr tempCellDirect[edi+12],1
 	mov dword ptr tempCellDirect[edi+16],-1
 	mov dword ptr tempCellDirect[edi+20],0
 	mov dword ptr tempCellDirect[edi+24],0
 	mov dword ptr tempCellDirect[edi+28],-1
	;make table tempCellAddValue dd 1,MazeSize,-1,-MazeSize
 	mov dword ptr tempCellAddValue[edi],1
	mov eax,wTempMaze
 	mov dword ptr tempCellAddValue[edi+4],eax
 	mov dword ptr tempCellAddValue[edi+8],-1
	neg eax
 	mov dword ptr tempCellAddValue[edi+12],eax
	mov dword ptr SourceWall,11110111111110111111110111111110b
	mov dword ptr OppositeWall,11111101111111101111011111111011b

	;----------初始化END----------

	;----------以下生成迷宫----------
	mov eax,xStartMaze
	mov xMaze,eax		;取任一起始点
	mov eax,yStartMaze
	mov yMaze,eax
	mov StackCount,0

RandomMaze22:
	
	mov eax,yMaze
	mul wTempMaze		;乘宽度
	add eax,xMaze		;计算编号
	mov esi,eax		;存偏移值

RandomMaze25:

	mov CellCount,4		;四边

RandomMaze30:
	xor eax,eax
	lea edi,LastCellDirect
	mov ecx,4
	rep stosd			;init

RandomMaze35:
	call ASeed		;get random number 
	mov ebx,4
	xor edx,edx
	div ebx			;edx = 0-3
	mov AddDecValue,edx
	shl edx,2		;x 4
	cmp  dword ptr LastCellDirect[edx],1	;是否已查?
	jz RandomMaze35
	mov dword ptr LastCellDirect[edx],1 ;marked
	mov eax,xMaze
	mov edx,AddDecValue
	shl edx,3		;x8
	add eax,tempCellDirect[edx]
	mov ebx,eax		;keep new X
	js @f			;超出左边界
	cmp eax,wTempMaze
	jae @f			;超出右边界
	mov eax,yMaze
	add eax,tempCellDirect[edx+4]
	mov edi,eax
	js @f			;超出上边界
	cmp eax,hTempMaze
	jae @f			;超出下边界

	; ebx,edi 			;new x, y
	
	mov eax,esi		;旧位置
	mov edx,AddDecValue
	shl edx,2			;x4
	add eax,tempCellAddValue[edx]	;取新值
	mov edx,addrMaze
	mov cl, byte ptr [eax+edx]  ;eax=新值,esi=旧值
	and cl,00001111b		;遮罩
	cmp cl,00001111b		;四边有墙?
	jz RandomMaze40		;找到

@@:	dec CellCount		;下一面墙
	jnz RandomMaze35

	;找不到四边有墙的新格
	dec StackCount
	jns @F
	;栈中没有新节点,已搜完,可离开
	jmp RandomMX  	;;;;;;;;;;;;;;;;;;;;;;;;;;离开
@@:
	mov eax,StackCount
	shl eax,2			;x4
	add eax,pStackMemory
	mov eax,[eax]  ;取出栈中的上一个节点
	mov esi,eax
	xor edx,edx
	div  hTempMaze
	mov xMaze,edx		;新位置
	mov yMaze,eax
	jmp RandomMaze25	

RandomMaze40:

	;找到四边有墙的新格
	;拆墙,edx记录哪一幅墙被拆
	;eax=新值,esi=旧值

	mov edx,AddDecValue
	mov cl,byte ptr SourceWall[edx]
	mov edx,addrMaze	
	and byte ptr [esi+edx],cl	;marked那一面墙被拆
	mov edx,AddDecValue
	mov cl,byte ptr OppositeWall[edx]
	mov edx,addrMaze	
	and byte ptr [eax+edx],cl	;marked那一面墙被拆

	mov xMaze,ebx		;新位置
	mov yMaze,edi
	mov esi,StackCount
	shl esi,2		;x4
	add esi,pStackMemory
	mov [esi],eax ;存新位置,push入
	inc StackCount
	jmp  RandomMaze22

RandomMX:
	invoke GlobalUnlock,pStackMemory 
	invoke GlobalFree,hStackMemory 

RandomMXX:
	ret

RandomMaze endp
;----------------------------------------------------------------------------------------------
;以下是Prim's Algorithm法制作迷宫,尚未完成
;http://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s-algorithm
;http://www.iverv.com/2015/09/unity-2randomized-kruskals-algorithm.html
;Prim's Algorithm
;Procedure
;Add starting node to closed set.
;For every node in the closed set, find all the adjacent nodes and calculate the distance to that node.
;If the node is already in the closed set, ignore it.
;Choose the node nearest to a node in the closed set
;Add it to the closed set.
;Repeat from step 2 until all nodes have been visited.

PrimMaze proc
	;net yet
	ret
PrimMaze endp
;----------------------------------------------------------------------------------------------
;乱数生成程序
ASeed   PROC

;Auto-Seeding Unscaled Random QWORD Generator - DednDave
;version 1, 11-2010
;version 2, 5-2013
;version 3, 6-2013
;version 4, 9-2013

;------------------------------
    mov     ecx,dwAsCnt
    mov     edx,dword ptr qwRnd64+4
    dec     ecx
    .if ZERO?
        rdtsc
        mov     cl,al
        mov dword ptr qwRnd64,eax
        mov     ch,1
        xor     edx,eax
    .endif
    mov     eax,1517746329
    mov     dwAsCnt,ecx
    mul     edx
    add     eax,dword ptr qwRnd64
    adc     edx,0
    xor     edx,eax
    mov dword ptr qwRnd64+4,eax
    mov dword ptr qwRnd64,edx
    ret

ASeed   ENDP

;###############################################################################################

;-------------------------------------------------------------------------
;use A*算法寻路

AStar_FindPath_proc proc xSource:DWORD,ySource:DWORD,xTarget:DWORD,yTarget:DWORD,wwUserMap:DWORD,hhUserMap:DWORD,addrUserMap:DWORD		;,addrAPath:DWORD

	LOCAL MinF_Value		:DWORD
	LOCAL CurrentFindX		:DWORD
	LOCAL CurrentFindY		:DWORD
	LOCAL CurrentFindOff	:DWORD
	LOCAL FindCount		:DWORD
	LOCAL CloseListLastCount	:DWORD
	LOCAL CloseListCurrentCount	:DWORD
	LOCAL OpenListCount	:DWORD
	LOCAL OpenListGValue	:DWORD
	LOCAL APath_Step_Count	:DWORD
	LOCAL vMapNodes		:DWORD
	LOCAL hApathMemory	:DWORD
	LOCAL pApathMemory	:DWORD
	LOCAL AddrApathOpen	:DWORD
	LOCAL AddrApathClose	:DWORD
	LOCAL tempApathAddValue[4]	:DWORD		
	LOCAL tempApathDirect[8]	:DWORD		
	LOCAL MaxOpenNum	:DWORD

	pushad
	mov eax,hhUserMap
	mul wwUserMap
	mov vMapNodes,eax
	mov  MaxOpenNum,10
	mov ebx,6 * 4 
	mul ebx
	mov AddrApathClose,eax
	shl eax,1			;x 2
	push eax
	add eax,1024		;ajust 1k
	invoke GlobalAlloc, GMEM_FIXED or GMEM_ZEROINIT,eax
	mov  hApathMemory,eax 
	invoke GlobalLock,hApathMemory
	mov pApathMemory,eax 
	mov AddrApathOpen,eax
	add AddrApathClose,eax
	pop ecx
	mov edi,hApathMemory
	mov eax,-1   
	shr ecx,2			; vMapNodes * 2 / 4
	rep stosd			;clear to -1
	;
	mov eax,AddrApathOpen	;get address
	push xSource
	pop [eax]
	push ySource
	pop [eax+4]
	mov dword ptr [eax+16],0FFFFH 	; F valule
	mov dword ptr [eax+20],0	 	; G valule
	mov CloseListLastCount,0		;0
	mov edi,0				;0
	
	; -------------- 初始化table start -----------------
	;make table tempApathDirect dd 1,0,0,1,-1,0,0,-1	
 	mov dword ptr tempApathDirect[edi],1
 	mov dword ptr tempApathDirect[edi+4],0		;0
 	mov dword ptr tempApathDirect[edi+8],0		;0
 	mov dword ptr tempApathDirect[edi+12],1
 	mov dword ptr tempApathDirect[edi+16],-1
 	mov dword ptr tempApathDirect[edi+20],0		;0
 	mov dword ptr tempApathDirect[edi+24],0		;0
 	mov dword ptr tempApathDirect[edi+28],-1

	;make table tempApathAddValue dd 1,wwUserMap,-1,-wwUserMap
 	mov dword ptr tempApathAddValue[edi],1
	mov eax,wwUserMap
 	mov dword ptr tempApathAddValue[edi+4],eax
 	mov dword ptr tempApathAddValue[edi+8],-1
	neg eax
 	mov dword ptr tempApathAddValue[edi+12],eax

	; -------------- 初始化table end -----------------

GhostF05:
	mov MinF_Value,0FFFFFFFFH		;min value
	mov FindCount,0			;count to 100
	mov esi,AddrApathOpen		;get address
GhostF10:
	;push esi
	mov eax,[esi]
	cmp eax,-1			;empty flag = -1
	jz GhostF30
GhostF20:
	mov eax,[esi+16]	;get F value
	cmp eax,MinF_Value
	jae  GhostF30
	; 找出最小值
	mov MinF_Value,eax	;save minimum value
	mov eax,FindCount	;那一个open list file
	mov CurrentFindOff,eax	;save it
GhostF30: 
	;pop esi
	add esi,6*4		;6 dword ,next open record
	inc FindCount
	;mov eax,vMapNodes
	mov eax,MaxOpenNum
	cmp FindCount,eax
	jb GhostF10
	cmp MinF_Value,-1
	jnz GhostF40

	;找不到open list ,离开
	invoke GlobalUnlock,pApathMemory
	invoke GlobalFree,hApathMemory
	popad 	
	mov eax,-1		;找不到
	ret

GhostF40:	;已找到最少f值的格
	mov eax,CurrentFindOff
	mov ebx, 6 * 4		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	mul ebx

	mov esi,AddrApathOpen
	add esi,eax

	push esi		;save
	mov eax,[esi]		; !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	mov CurrentFindX,eax
	mov eax,[esi+4]
	mov CurrentFindY,eax
	mov eax,CloseListLastCount
	mul ebx
	add eax,AddrApathClose
	mov edi,eax
	mov ebx,eax	;save it		;;;;;;;;;;;;;;;;;;;;;;;;;;;
	mov ecx,6		; 1 record
	rep movsd		; 1 record
	pop esi			;restore

	inc CloseListLastCount
	mov dword ptr [esi],-1	;已移到close list, 设 -1 表示空
	;
	;开始查方向 !
	;查一下墙是否通!!!

GhostF45:
	mov ecx,0			;查4方向
	mov esi,ebx		;------------restore new esi, point to close list
	mov eax,CurrentFindY
	mul wwUserMap
	add eax,CurrentFindX
	add eax,addrUserMap		;指向User Map的x,y
	mov  al,[eax]		;最当前格
GhostF45a:
	push ecx
	push esi
	rcr al,1			
	push eax
	jc GhostF70		;没有墙,可通

 	; 没有墙,可通, 0=right,1=down,2=left,3=up
	;make table tempApathDirect dd 1,0,0,1,-1,0,0,-1	

	mov edi,CurrentFindY
	mov ebx,CurrentFindX

	mov edx,ecx		;0,1,2,3
	shl edx,3			;x8
	;
	lea edx,[edx+tempApathDirect]
	mov eax,[edx]		
	add ebx,eax		;x-axis
	mov eax,[edx+4]	
	add edi,eax			;y-axis
	; check target x,y
	cmp ebx,xTarget		;target X
	jnz @f
	cmp edi,yTarget	;target Y
	jnz @f
	pop eax
	pop esi
	pop ecx
	jmp GhostF90	;Found Target 
@@:
	;不是block 又不是目的 than check close, then open ,若是open	
	;ebx,edi 保存新位置 x, y
	mov CloseListCurrentCount,0

GhostF46:
	mov ecx,CloseListCurrentCount
	mov eax,ecx
	shl eax,3			;x8
	shl ecx,4			;x 16
	add ecx,eax
	add ecx,AddrApathClose
	cmp [ecx],ebx	;比较close list 的格子x
	jnz GhostF47
	cmp [ecx+4],edi	;比较close list 的格子y
	jnz GhostF47
	; 在close list
	jmp  GhostF70

GhostF47: inc CloseListCurrentCount
	mov eax,CloseListLastCount
	cmp CloseListCurrentCount,eax
 	jb GhostF46

	;不在close list内, check 是否在open list
	;Ghost_FindPath_count equ MapNodes
	;Ghost_FindPath_Open 	
	mov OpenListCount,0		;0- ???

GhostF48:
	mov ecx,OpenListCount
	mov eax,ecx	
	shl eax,3			;x8
	shl ecx,4			;x 16
	add ecx,eax
	add ecx,AddrApathOpen
	cmp [ecx],ebx	;比较open list 的格子x
	jnz GhostF49		;不在open list , 去GhostF49
	cmp [ecx+4],edi	;比较open list 的格子y
	jnz GhostF49		;不在open list , 去GhostF49

	;在 open list
	;如果 G 值更小，则把那个方格的父亲设为当前方格(我们选中的方格)
	;然后重新计算那个方格的 F 值和 G 值。

	mov eax,[ecx+20]	;原有的g值,比较当前g值
	mov OpenListGValue,eax

	mov eax,Direction1GValue		;取
	add eax,[esi+20]			;当前g 值

	cmp OpenListGValue,eax	;原有的g值,比较当前g值
	jbe  GhostF70			;跳出回圈
	;([esi+16]=F)([esi+20]=G

	push dword ptr [esi]			;存入当前close list位置x
	pop [ecx+8]	;把我的父位置,取代open list的父位置
	push dword ptr [esi+4]			;存入当前位置y
	pop [ecx+12]

	mov [ecx+20],eax	;put new G value
	sub OpenListGValue,eax
	xchg OpenListGValue,eax
	sub [ecx+16],eax	;ajust F value
	;跳出回圈
	jmp GhostF70

GhostF49: ;next
	inc OpenListCount
	mov eax,MaxOpenNum
	cmp OpenListCount,eax
	jb GhostF48

	;不在open list,要放入open list
	mov OpenListCount,0	
GhostF50:
	mov ecx,OpenListCount
	mov eax,ecx	
	shl eax,3			;x8
	shl ecx,4			;x 16
	add ecx,eax

	add ecx,AddrApathOpen
	cmp dword ptr[ecx],-1
	jnz GhostF55			;已有资料
	; 找到空位
	;([esi],[esi+4])([esi+8],[esi+12])([esi+16]=F)([esi+20]=G(总路径计值)
	;position,parent (位置,指向父), F Value = G +H, G

	cmp dword ptr[ecx+4],-1
	jnz @f
	inc MaxOpenNum
@@:
	pushad
	mov  [ecx],ebx	;put curent X
	mov  [ecx+4],edi	;put current Y

	mov eax,[esi]
	mov  [ecx+8],eax	;put parent X , 父位置x
	mov eax,[esi+4]
	mov [ecx+12],eax	;put current Y, 父位置y

	mov eax,Direction1GValue		;取 10
	add eax,[esi+20]			;当前g 值

	mov [ecx+20],eax	;put current g value
	; 计算h值和F值
	;ebx, edi
	sub ebx,xTarget
	jns @f
	neg ebx
@@:
	sub edi,yTarget
	jns @f
	neg edi
@@:
	add ebx,edi				;get H
	; x 10
	mov edi,ebx			;keep 1
	shl edi,1				;x2
	shl ebx,3				;x8
	add ebx,edi				;x10
	add ebx,[ecx+20]	; get F = H + G
	mov [ecx+16],ebx	; save F
	popad
	jmp GhostF70			;做了1/4,下一个
GhostF55:	
	inc OpenListCount
	;mov eax,vMapNodes
	mov eax,MaxOpenNum
	cmp OpenListCount,eax
	jb GhostF50
GhostF70:
	;Blocked,next
	pop eax
	pop esi
	pop ecx
	inc ecx			;0,1,2,3 or 0-7 ?
	cmp ecx,4			;AstarList.AstarDirectionCount
	jb GhostF45a

	;四个相邻方格查完
	jmp GhostF05		;回去再在open list找 最少f value				
	
	;Found target !!
	;由 CurrentFindX,CurrentFindY 开始回头加入list 中

GhostF90:
	mov APath_Step_Count,0
	push edi			;save target		;15,5
	push ebx
	add APath_Step_Count,2	
	
	push dword ptr [esi+4]		;nearest target y	;14,5
	push dword ptr [esi]		;nearest target X
	add APath_Step_Count,2	

	mov edi,dword ptr [esi+4]
	mov ebx,dword ptr [esi]
	cmp ebx,xSource
	jnz @F
	cmp edi,ySource		
	jz GhostF98		;来源和目的相邻

@@:	
	mov ebx,[esi+8]		;get new parent X	;13,5
	mov edi,[esi+12]		;get new parent Y
GhostF91:
	mov OpenListCount,0		;0- MapNodes
GhostF92:
	push edi					;13,5
	push ebx
	add APath_Step_Count,2
	cmp ebx,xSource
	jnz @F
	cmp edi,ySource
	jz GhostF98		;back to Source !!!!!
@@:
	;mov ebx,[esi+8]		;get new parent X
	;mov edi,[esi+12]		;get new parent Y

@@:
	mov ecx,OpenListCount
	mov eax,ecx	
	shl eax,3			;x8
	shl ecx,4			;x 16
	add ecx,eax
	add ecx,AddrApathClose
	cmp [ecx],ebx	;比较open list 的格子x
	jnz GhostF96
	cmp [ecx+4],edi	;比较open list 的格子y
	jnz GhostF96

GhostF95:	;found parent !!!!!
	mov esi,ecx
	mov ebx, [esi+8]		;get new parent X
	mov edi, [esi+12]	;get new parent Y
	jmp GhostF91
GhostF96:
	inc OpenListCount
	mov eax,vMapNodes
	cmp OpenListCount,eax
	jb @b
GhostF98:	
	;输出路径
	mov ecx,APath_Step_Count
	shr ecx,1	
	mov APath_Step_Count,ecx
GhostF100:
	pop ebx		;get y
	pop eax		;get x
	mul wwUserMap
	add eax,ebx
	add eax,addrUserMap
	or byte ptr [eax], 10000000b
	cmp ecx,APath_Step_Count
	jnz @f
	or byte ptr [eax], 01000000b
@@:	cmp ecx,1
	jnz @f
	or byte ptr [eax], 01000000b
@@:
	loop GhostF100

	invoke GlobalUnlock,pApathMemory
	invoke GlobalFree,hApathMemory
	popad 	
	mov eax,APath_Step_Count
	ret

AStar_FindPath_proc endp
;-------------------------------------------------------------------------
print_AX proc
	mov ecx,0 ;清0
	mov ebx,10 ;除法准备
Pax1:
	mov edx,0 ;清0
	div ebx ;eax /10 ,若1234 ,除10后,dl得余数4,
	push edx ;保存, ax=1234,依次保存4,3,2,1
	inc ecx ;累加个数
	or eax,eax ;是否已除尽
	jnz Pax1 ;不是,再除
Pax2:
	pop eax  ;后入先出,先印出第一数,然后第二....
	or al,30h ;转ascii
	stosb ;存入字串缓冲
	loop Pax2 ;下一个
	ret
print_AX endp
;----------------------------------------------------------------------------------------------
ClearPath proc
		push eax
		push ecx
		push edx
		push esi

		lea esi,MazeBoard
		mov eax,wUserMap
		mul hUserMap
		mov ecx,eax
@@:		and byte ptr [esi],00001111b	;clear bit 7
		;and byte ptr [esi],01111111b	;clear bit 7
		inc esi
		loop @b
		
		pop esi
		pop edx
		pop ecx
		pop eax
		ret

ClearPath endp
;----------------------------------------------------------------------------------------------
CheckNeighbour proc

	LOCAL WhichDirectionX		:DWORD	

	pushad
	xor ecx,ecx
	mov WhichDirectionX,2		;right,down,left,up (0,1,2,3)
	mov eax,SourceTargetTempPosition[ecx]
	sub eax,SourceTargetTempPosition[ecx+8]
	jns @f
	neg eax	
	mov WhichDirectionX,0		;right
	jmp CheckN20	

@@:	jnz  CheckN20		;正数,表示right,WhichDirectionX=0
	mov WhichDirectionX,3		;up 


CheckN20:
	mov ebx,SourceTargetTempPosition[ecx+4]
	sub ebx,SourceTargetTempPosition[ecx+12]
	jns @f			;0或正 
	neg ebx
	mov WhichDirectionX,1		;down
@@:	
	add eax,ebx
	cmp eax,1		;距离大于1始可以寻径
	jae CheckN30

	;再查是否有隔,若有隔,可寻

	mov ApathSetCount,1		;相邻,无墙,不做动作
	popad
	mov eax,-1
	ret

CheckN30:
	popad
	ret

CheckNeighbour endp
;----------------------------------------------------------------------
GetSystemtimeCount proc
	rdtsc
	ret
GetSystemtimeCount endp
;----------------------------------------------------------------------
end start 
;程式结束